# LeetCode 743、网络延迟时间
# 一、题目描述
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
img
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
提示：
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- 所有
(ui, vi)对都 互不相同（即，不含重复边）
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 网络延迟时间（LeetCode 743）：https://leetcode.cn/problems/network-delay-time/
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
// 1、默认任何一个网络节点到其它任何一个网络节点的传递时间为无穷大
// 这样在对比过程中，获取到一个具体的数值时才能通过取较小值的方式获取到该值
// 2、更新最短距离的时候，会计算两个距离之和，为了防止溢出
// 采取除以 2 的操作
// 3、根据题目的提示，n 最大为 100，传递时间最大为 100
// 所以，INF 的值设置为 10000、10001、10002、10003 等也是可以的
int INF = Integer.MAX_VALUE / 2;
// 使用邻接矩阵存储边信息
int[][] g = new int[n][n];
// 初始化
// 默认节点之间的传递时间为 INF
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], INF);
}
// 遍历列表 times
// times 列表里面的元素是一个一维数组
// 一维数组里面包含三个元素
// [ u , v , w ]
// u 表示源节点
// v 表示目标节点
// w 表示 u 到 v 的传递时间
for (int[] t : times) {
// 根据题目的说明
// 由于 u 、v 的标记范围是 1 到 n
// 而数组下标索引是从 0 开始的
// 所以需要进行一个计算
int uIndex = t[0] - 1;
int vIndex = t[1] - 1;
// 把传递时间更新到图中
g[uIndex][vIndex] = t[2];
}
// 开始计算所有点到源点的距离
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
// 根据我们的视频动画演示，可以利用一个数组记录
int[] dist = new int[n];
// 默认值也可以设置为一个无穷大的值
Arrays.fill(dist, INF);
// 设置源点到源点的值
// 由于从 k 开始，所以该点距离设为 0，也即源点
// 即源点的最短距离是 0
dist[k - 1] = 0;
// 为了避免节点被反复计算
// 设置一个数组，用来记录节点是否被更新过
boolean[] visited = new boolean[n];
// 迭代 n 次
// 第一次计算可以计算出从源点 k 到源点 k 的距离为 0
// 以示例 1 作为输入，会设置 visited[1] = true
for (int i = 0; i < n; i++) {
// 每次都去寻找出「最短距离最小」且「未被更新」的点来
// 这个点一开始不知道在哪个位置
// 于是可以默认设置为一个不存在的值
// -1、-2、-3 等都是可以的
int x = -1;
// 访问 visited 里面的所有元素
// 定位出 x 这个节点应该是在哪个位置
for (int j = 0; j < n; j++) {
// 1、这个节点需要没有被更新过
// 2.1、x 还没有确定在哪个节点位置
// 2.2、x 确定了，但发现有个节点距离源点还更近
if (!visited[j] && (x == -1 || dist[j] < dist[x])) {
// 定位了 x 的位置
x = j;
}
}
// 跳出上面这个 for 循环之后
// 已经明确知道 x 在哪个节点位置了
// 标记 x 为 true
visited[x] = true;
// 依托于这个节点，从这个节点出发，更新其它点的距离
for (int p = 0; p < n; p++) {
// dist[p] 代表从「源点/起点」到 p 的最短距离
// 对比之前存储的值 dist[p]
// 和从源点到 x 的最短距离，再从 x 出发到 p 的距离两者的和
dist[p] = Math.min(dist[p], dist[x] + g[x][p]);
}
}
// 找到距离最远的点
int ans = -1;
// 在 dist 找出那个最大的值来
for( int i = 0 ; i < n ; i++){
ans = Math.max(dist[i], ans);
}
// 如果发现找出的距离是 INF
// INF 是初始化的值，表示到不了，就返回 -1
return ans == INF ? -1 : ans;
}
}
# **2、**C++ 代码
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
// 1、默认任何一个网络节点到其它任何一个网络节点的传递时间为无穷大
// 这样在对比过程中，获取到一个具体的数值时才能通过取较小值的方式获取到该值
// 2、更新最短距离的时候，会计算两个距离之和，为了防止溢出
// 采取除以 2 的操作
// 3、根据题目的提示，n 最大为 100，传递时间最大为 100
// 所以，INF 的值设置为 10000、10001、10002、10003 等也是可以的
int INF = INT_MAX / 2;
// 使用邻接矩阵存储边信息
// 初始化
// 默认节点之间的传递时间为 INF
vector<vector<int>> g(n, vector<int>(n, INF));
// 遍历列表 times
// times 列表里面的元素是一个一维数组
// 一维数组里面包含三个元素
// [ u , v , w ]
// u 表示源节点
// v 表示目标节点
// w 表示 u 到 v 的传递时间
for (auto &t : times) {
// 根据题目的说明
// 由于 u 、v 的标记范围是 1 到 n
// 而数组下标索引是从 0 开始的
// 所以需要进行一个计算
int uIndex = t[0] - 1;
int vIndex = t[1] - 1;
// 把传递时间更新到图中
g[uIndex][vIndex] = t[2];
}
// 开始计算所有点到源点的距离
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
// 根据我们的视频动画演示，可以利用一个数组记录
// 默认值也可以设置为一个无穷大的值
vector<int> dist(n, INF);
// 设置源点到源点的值
// 由于从 k 开始，所以该点距离设为 0，也即源点
// 即源点的最短距离是 0
dist[k - 1] = 0;
// 为了避免节点被反复计算
// 设置一个数组，用来记录节点是否被更新过
vector<bool> visited(n);
// 迭代 n 次
// 第一次计算可以计算出从源点 k 到源点 k 的距离为 0
// 以示例 1 作为输入，会设置 visited[1] = true
for (int i = 0; i < n; i++) {
// 每次都去寻找出「最短距离最小」且「未被更新」的点来
// 这个点一开始不知道在哪个位置
// 于是可以默认设置为一个不存在的值
// -1、-2、-3 等都是可以的
int x = -1;
// 访问 visited 里面的所有元素
// 定位出 x 这个节点应该是在哪个位置
for (int j = 0; j < n; j++) {
// 1、这个节点需要没有被更新过
// 2.1、x 还没有确定在哪个节点位置
// 2.2、x 确定了，但发现有个节点距离源点还更近
if (!visited[j] && (x == -1 || dist[j] < dist[x])) {
// 定位了 x 的位置
x = j;
}
}
// 跳出上面这个 for 循环之后
// 已经明确知道 x 在哪个节点位置了
// 标记 x 为 true
visited[x] = true;
// 依托于这个节点，从这个节点出发，更新其它点的距离
for (int p = 0; p < n; p++) {
// dist[p] 代表从「源点/起点」到 p 的最短距离
// 对比之前存储的值 dist[p]
// 和从源点到 x 的最短距离，再从 x 出发到 p 的距离两者的和
dist[p] = min(dist[p], dist[x] + g[x][p]);
}
}
// 找到距离最远的点
int ans = -1;
// 在 dist 找出那个最大的值来
for( int i = 0 ; i < n ; i++){
ans = max(dist[i], ans);
}
// 如果发现找出的距离是 INF
// INF 是初始化的值，表示到不了，就返回 -1
return ans == INF ? -1 : ans;
}
};
# 3、Python 代码
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 1、默认任何一个网络节点到其它任何一个网络节点的传递时间为无穷大
# 这样在对比过程中，获取到一个具体的数值时才能通过取较小值的方式获取到该值
# 2、更新最短距离的时候，会计算两个距离之和，为了防止溢出
# 采取除以 2 的操作
# 3、根据题目的提示，n 最大为 100，传递时间最大为 100
# 所以，INF 的值设置为 10000、10001、10002、10003 等也是可以的
# 使用邻接矩阵存储边信息
g = [[float('inf')] * n for _ in range(n)]
# 初始化
# 默认节点之间的传递时间为 INF
# 遍历列表 times
# times 列表里面的元素是一个一维数组
# 一维数组里面包含三个元素
# [ u , v , w ]
# u 表示源节点
# v 表示目标节点
# w 表示 u 到 v 的传递时间
for x, y, time in times:
g[x - 1][y - 1] = time
# 开始计算所有点到源点的距离
# dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
# 根据我们的视频动画演示，可以利用一个数组记录
dist = [float('inf')] * n
# 默认值也可以设置为一个无穷大的值
# 设置源点到源点的值
# 由于从 k 开始，所以该点距离设为 0，也即源点
# 即源点的最短距离是 0
dist[k - 1] = 0
# 为了避免节点被反复计算
# 设置一个数组，用来记录节点是否被更新过
visited = [False] * n
# 迭代 n 次
# 第一次计算可以计算出从源点 k 到源点 k 的距离为 0
# 以示例 1 作为输入，会设置 visited[1] = true
for _ in range(n) :
# 每次都去寻找出「最短距离最小」且「未被更新」的点来
# 这个点一开始不知道在哪个位置
# 于是可以默认设置为一个不存在的值
# -1、-2、-3 等都是可以的
x = -1
# 访问 visited 里面的所有元素
# 定位出 x 这个节点应该是在哪个位置
for j, u in enumerate(visited):
# 1、这个节点需要没有被更新过
# 2.1、x 还没有确定在哪个节点位置
# 2.2、x 确定了，但发现有个节点距离源点还更近
if not u and (x == -1 or dist[j] < dist[x]):
# 定位了 x 的位置
x = j
# 跳出上面这个 for 循环之后
# 已经明确知道 x 在哪个节点位置了
# 标记 x 为 true
visited[x] = True
# 依托于这个节点，从这个节点出发，更新其它点的距离
for p, time in enumerate(g[x]):
dist[p] = min(dist[p], dist[x] + time)
# 找到距离最远的点
# 在 dist 找出那个最大的值来
ans = max(dist)
# 如果发现找出的距离是 INF
# INF 是初始化的值，表示到不了，就返回 -1
return ans if ans < float('inf') else -1